package com.yan_jiu_sheng.LeetCodeHot100.AC;

import java.util.Arrays;

/**
 * https://leetcode.cn/problems/product-of-array-except-self/?envType=study-plan-v2&envId=top-100-liked
 * 通过
 *
 * @author yulongTian
 * @create 2024-05-28 15:29
 */
public class Test16 {
    public static void main(String[] args) {
//        int[] nums = {1, 2, 3, 4};
        int[] nums = {-1, 1, 0, -3, 3};
        System.out.println(Arrays.toString(new Test16().productExceptSelf(nums)));


    }

    /**
     * 前缀和后缀乘积
     * 空间复杂度 O(n)
     *
     * @param nums
     * @return
     */
    public int[] productExceptSelf(int[] nums) {
//        int[] res = new int[nums.length];
        int[] preMulti = new int[nums.length];
        int[] latterMulti = new int[nums.length];
        preMulti[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            preMulti[i] = preMulti[i - 1] * nums[i];
        }
        latterMulti[nums.length - 1] = nums[nums.length - 1];
        for (int i = nums.length - 2; i >= 0; i--) {
            latterMulti[i] = latterMulti[i + 1] * nums[i];
        }

        for (int i = 0; i < nums.length; i++) {
            // 前者
            int pre;
            if (i - 1 < 0) {
                pre = 1;
            } else {
                pre = preMulti[i - 1];
            }

            // 后者
            int latter;
            if (i + 1 >= nums.length) {
                latter = 1;
            } else {
                latter = latterMulti[i + 1];
            }
            nums[i] = pre * latter;
        }

        return nums;
    }

}
